/*
 * @lc app=leetcode.cn id=212 lang=cpp
 *
 * [212] 单词搜索 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{

    bool search(const vector<vector<char>> &board,
                vector<vector<bool>> &visited,
                int x, int y,
                const string &word,
                int start)
    {
        if (start == word.size())
            return true;

        int arr1[] = {0, 0, -1, 1};
        int arr2[] = {-1, 1, 0, 0};
        for (int i = 0; i < 4; i++)
        {
            int new_x = x + arr1[i];
            int new_y = y + arr2[i];
            if (new_x >= 0 && new_x < board.size() && new_y >= 0 && new_y < board[0].size())
            {
                if (!visited[new_x][new_y] && board[new_x][new_y] == word[start])
                {
                    visited[new_x][new_y] = true;
                    if (search(board, visited, new_x, new_y, word, start + 1))
                    {
                        visited[new_x][new_y] = false;

                        return true;
                    }

                    visited[new_x][new_y] = false;
                }
            }
        }
        return false;
    }

    bool isInBoard(const vector<vector<char>> &board,
                   const map<char, vector<pair<int, int>>> char2pois,
                   const string &word)
    {
        auto it = char2pois.find(word[0]);
        if (it != char2pois.end())
        {
            auto pois_vec = it->second;
            for (auto &pois : pois_vec)
            {
                vector<vector<bool>> visited(
                    board.size(),
                    vector<bool>(board[0].size(), false));

                visited[pois.first][pois.second] = true;
                if (search(board, visited, pois.first, pois.second, word, 1))
                {
                    return true;
                }
            }
        }
        return false;
    }

    map<char, vector<pair<int, int>>> recordCharPosition(const vector<vector<char>> &board,
                                                         set<char>& s)
    {
        map<char, vector<pair<int, int>>> m;
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                m[board[i][j]].push_back(std::make_pair(i, j));
                s.insert(board[i][j]);
            }
        }
        return m;
    }

public:
    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {
        set<char> s;

        auto m = recordCharPosition(board, s);

        vector<string> ans;
        for (auto &word : words)
        {
            bool flag = true;
            for(auto c : word)
            {
                if(s.find(c) == s.end())
                {
                    flag = false;
                }
            }
            if (flag && isInBoard(board, m, word))
            {
                ans.push_back(word);
            }
        }

        // std::sort(m.begin(), m.end(), [](const string& s1, const string& s2)->bool{
        //     return strcmp(s1.c_str(), s2.c_str()) > 0 ? true : false;
        // });

        // std::sort(ans.begin(), ans.end());

        return ans;
    }
};

// int main(int argc, char const *argv[])
// {
//     vector<vector<char>> board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
//     vector<string> words = {"oath","pea","eat","rain"};

//     auto v = Solution().findWords(board, words);
//     for(auto& s : v)
//     {
//         cout << s << endl;
//     }

//     return 0;
// }

// @lc code=end
